39. 组合总和

发表于 | 分类于 | 阅读次数：

链接：https://leetcode-cn.com/problems/combination-sum/

题目描述

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1:

1
2
3
4
5
6
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

示例 2:

1
2
3
4
5
6
7
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

这道题是一个回溯法中变形的组合类的题，变形的地方在于，可以取重复的数字。

递归结构

递归边界

1
2
if f(n) == target:
        return result

递归参数

  • start：开始位置
  • result: 单次递归结果
  • result_all：最终结果
  • candidates
  • target

剪枝

本题需要进行剪枝：

  1. 第一个是对candidates进行一个排序，这样当判断：
    1
    f(n) = f(n-1) + num > target

这时候，这个num后面的数字由于经过排序，必然加起来也是大于target的，所以直接break就可以了。

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution(object):
    
    def __init__(self):
        self.result_all = None
    
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        self.result_all = []
        candidates = sorted(candidates)
        self.dfs(0, candidates, target, [])
        return self.result_all
        
        
        
    def dfs(self, start, candidates, target, result):
        if sum(result) == target:
            self.result_all.append(result[:])
            return
        
        for i in range(start, len(candidates)):
            num = candidates[i]
            if sum(result) + num > target:
                break
            result.append(num)
            self.dfs(i, candidates, target, result)
            result.pop()
        return